1673E - Power or XOR - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
//取模运算多的时候注意ll的效率
#define int long long
#define ull unsigned long long
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define Rep(i,a,b) for (int i=a;i>=(b);i--)
#define pb push_back
#define mid(l,r) l+((r-l)>>1)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define db double
#define vi vector<int>
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
#define SWAP(a,b) a^=b^=a^=b
#define lowbit(x) ((x)&-(x))
#define el '\n'
// template<typename T>T
int gcd(int a,int b){return b?gcd(b,a%b):a;}
//Think twice,code once
const int N=1<<20;
int cnt[N],ans[N];
int calc_cnt(int x){
    int ret=0;
    while(x%2==0)++ret,x>>=1;
    return ret;
}
void pre_calc(){
    rep(i,1,N)cnt[i]=calc_cnt(i);
    rep(i,2,N)cnt[i]+=cnt[i-1];
}
int parity(int n,int m){
    if(!n)return 1;
    if(!m)return 0;
    return cnt[n-1]-cnt[m-1]-cnt[n-m]==0;
}
void solve(){
    pre_calc();
    int n,k;cin>>n>>k;
    vector<int>a(n);
    rep(i,0,n)cin>>a[i];
    int mx=0;
    rep(i,0,n){
        int mul=1;
        rep(j,i,n){
            if(j!=i&&a[j]>=20)break;
            mul*=(j==i?a[j]:1ll<<a[j]);
            if(mul>=N)break;
            int cnt=n-j+i-1-(i!=0)-(j!=n-1),must=(i!=0)+(j!=n-1);
            if(cnt<k-must)continue;
// cout<<i<<' '<<j<<' '<<mul<<' '<<cnt<<' '<<k-must<<' '<<must<<el;
            mx=max(mx,mul);
            ans[mul]^=parity(cnt,k-must);
        }
    }
    while(mx&&ans[mx]==0)--mx;
    Rep(i,mx,0)cout<<ans[i];
}
signed main(){
    ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}